package Link;

import java.util.List;

public class leet_23 {
}

class Solution_23 {
    public ListNode mergeKLists(ListNode[] lists) {
        ListNode result = mergeKListFunc(lists);
        return result;
    }

    /**
     * 直接2个2个合并  暴力法
     * @param lists
     * @return
     */
    public ListNode mergeKListFunc(ListNode[] lists){
        ListNode result = null;
        for(int i=0; i<lists.length; i++){
            result = mergeTwo(result, lists[i]);
        }
        return result;
    }

    /**
     * 合并2个ListNode
     * @param tmp1
     * @param tmp2
     * @return
     */
    public ListNode mergeTwo(ListNode tmp1, ListNode tmp2){
        if(tmp1==null || tmp2==null){
            if(tmp1==null){
                return tmp2;
            }
            return tmp1;
        }
        // 合并
        ListNode head = new ListNode(0);
        ListNode tail = head;
        while(tmp1!=null && tmp2!=null){
            if(tmp2.val > tmp1.val){
                // 谁小head结点指向谁
                tail.next = tmp1;
                tmp1 = tmp1.next;
            }else{
                tail.next = tmp2;
                tmp2 = tmp2.next;
            }
            tail = tail.next;
        }
        if(tmp1==null){
            tail.next = tmp2;
        }else{
            tail.next = tmp1;
        }
        return head.next;
    }


    /**
     * 分治法
     */
    public ListNode mergeKListDivide(ListNode[] lists) {
        return null;
    }

}